#include <iostream>
using namespace std;
#include <vector>

void merge(vector<int>& v, vector<int>& tmp, int left, int mid, int right)
{
	//左半区的第一个元素下标
	int l_pos = left;
	//右半区的第一个元素下标
	int r_pos = mid + 1;
	//存进辅助元素的当前下标
	int pos = left;
	//合并
	while (l_pos <= mid && r_pos <= right)
	{
		if (v[l_pos] < v[r_pos])
			tmp[pos++] = v[l_pos++];
		else
			tmp[pos++] = v[r_pos++];
	}
	//当右半区没有元素了，直接将左半区剩余元素移过来
	while (l_pos <= mid)
	{
		tmp[pos++] = v[l_pos++];
	}
	//当左半区没有元素了，直接将右半区剩余元素移过来
	while (r_pos <= mid)
	{
		tmp[pos++] = v[r_pos++];
	}
	//最后将数据移到原数组中
	//不能使用assign，会改变size
	for (int i = 0; i < pos; i++)
	{
		v[i] = tmp[i];
	}
}

void mSort(vector<int>& v, vector<int>& tmp, int left, int right)
{
	//如果序列中只有一个数，则说明已经有序了，则不需要被归并
	if (left == right)
		return;
	
	//序列中间的那个数的下标
	int mid = (left + right) / 2;

	//继续划分左半区
	mSort(v, tmp, left, mid);

	//继续划分右半区
	mSort(v, tmp, mid + 1, right);

	//最后将左右半区进行合并
	merge(v, tmp, left, mid, right);
}

void MergeSort(vector<int>& v, const int& size)
{
	//创建一个辅助数组来存数据
	vector<int>* tmp = new vector<int>;
	tmp->assign(size, 0);

	mSort(v, *tmp, 0, size - 1);

	delete tmp;
	tmp = nullptr;
}

int main()
{
	vector<int> v;
	for (int i = 9; i >= 1; i--)
	{
		v.push_back(i);
	}
	cout << "排序前:" << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}

	cout << endl;

	cout << "排序后:" << endl;
	MergeSort(v, v.size());
	for (auto e : v)
	{
		cout << e << " ";
	}
	return 0;
}